/**
 * 该模块实现了一个有序 Set 。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.collections.TreeSet;

import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.ICollection;
import system.collections.IComparer;
import system.collections.Comparer;

import system.collections.RBTree;
import system.collections.Stack;

import system.Exception;

import system.math.Math;

version(unittest)
{
	import system.collections.ArrayList;
}

/**
 * 提供一个有序 Set 集合。
 * Comments:
 *		此实现为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
 *		红黑树实现。
 */
public class TreeSet(T) : IEnumerable!(T), ICollection!(T)
{
	package int theVersion;
	package RBTree!(T) theTree;

	/**
	 * 构造一个新的空 TreeSet，它根据指定比较器进行排序。
	 * Params:
	 *		comparer = 用来对此 Set 进行排序的比较器。
	 *		默认使用 DefaultComparer(T)。
	 * Comments:
	 *		插入到该 Set 的所有元素都必须能够由指定比较器进行相互比较。
	 */
	public this(IComparer!(T) comparer = DefaultComparer!(T).getInstance())
	in
	{
		assert(comparer !is null);
	}
	body
	{
		theTree = new RBTree!(T)(comparer);
	}

	/**
	 * 构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的迭代顺序进行排序。
	 * Comments:
	 *		插入该 Set 的所有元素都必须能够由默认比较器进行相互比较或者正确实现 opCmp 。
	 *		Note: collection 内的元素仅仅保留非重复值。
	 */
	public this(IEnumerable!(T) collection)
	in
	{
		assert( collection !is null );
	}
	body
	{
		theTree = new RBTree!(T)(DefaultComparer!(T).getInstance());
		foreach(item; collection)
		{
			theTree.add(item);
		}
	}

	/*
	 * 实现 IEnumerable(T) 接口。
	 */

	public final Enumerator  getEnumerator()
	{
		return new Enumerator();
	}

	public final int opApply (int delegate (ref T value) dg)
	{
		auto scope enumerator = new Enumerator();
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	public final class Enumerator : IEnumerator!(T)
	{
		private int modCount;
		private RBTreeNode!(T) currentNode;
		private Stack!(RBTreeNode!(T)) stack;
		package this()
		{
			modCount = theVersion;
			stack = new Stack!(RBTreeNode!(T))(2 * (cast(int)log(cast(double)(theTree.count+1))));
			initialize();
		}

		public bool moveNext()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			if(stack.count == 0)
			{
				currentNode = null;
				return false;
			}

			currentNode = stack.pop();

			for(auto node = currentNode.right; node !is null; node = node.left)
			{
				stack.push(node);
			}
			return true;
		}

		public T current()
		{
			if(currentNode !is null)
				return currentNode.value;
			return T.init;
		}

		public void reset()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			stack.clear();
			initialize();
		}

		private void initialize()
		{
			currentNode = null;
			for(auto node = theTree.root; node !is null; node = node.left)
			{
				stack.push(node);
			}
		}
	}

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 检测 TreeSet 是否为空。
	 */
	public final bool isEmpty()
	{
		return theTree.root is null;
	}

	/**
	 * 返回 TreeSet 的元素数。
	 */
	public final int count()
	{
		return theTree.count();
	}

	/**
	 * 检测 TreeSet 是否只读。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 将指定的元素添加到此 Set（如果该元素尚未存在于 Set 中）。
	 * Params:
	 * 		item = 要添加到此 Set 的元素。
	 * Returns:
	 *		true，当成功插入时。
	 * Throws:
	 *		ArgumentException，当有重复值插入时。
	 * Comments:
	 *		插入到该 Set 的所有元素都必须能够由指定比较器进行相互比较。
	 */
	public final bool add(T item)
	{
		auto size = theTree.count;
		theTree.add(item);
		if(size == theTree.count)
			return false;
		theVersion++;
		return true;
	}

	/**
	 * 清空此 TreeSet 。
	 */
	public final void clear()
	{
		theTree.clear();
		theVersion++;
	}

	/**
	 * 将指定的元素从 Set 中移除（如果该元素存在于此 Set 中）。
	 * Params:
	 * 		item = 将从此 Set 中移除的对象（如果存在）。
	 * Returns:
	 *		如果此 Set 包含指定元素，返回 true。
	 *		如果此 Set 未包含指定元素，则该调用不改变此 Set，并返回 false 。
	 */
	public final bool remove(T item)
	{
		auto size = theTree.count();
		theTree.remove(item);
		if(size == theTree.count())
		{
			return false;
		}
		theVersion++;
		return true;
	}

	/**
	 * 检测此 Set 是否包含指定的元素。
	 */
	public final bool contains(T item)
	{
		return theTree.contains(item);
	}

	/**
	 * 将此 Set 中的元素拷贝进一维数组中。
	 * Params:
	 *		array = 要放入元素的一维数组。
	 * Throws:
	 *		Error，当 array 为 null 或 array 的长度小于此 Set 的 count 时。
	 */
	public final void toArray(T[] array)
	in
	{
		assert(array !is null);
		assert(array.length >= this.count());
	}
	body
	{
		Stack!(RBTreeNode!(T)) stack;
		RBTreeNode!(T) current;
		int i;
		void initialize()
		{
			i = 0;
			stack = new Stack!(RBTreeNode!(T))(2 * (cast(int)log(cast(double)(theTree.count+1))));
			current = null;
			for(auto node = theTree.root; node !is null; node = node.left)
			{
				stack.push(node);
			}
		}

		bool moveNext()
		{
			if(stack.count == 0)
			{
				current = null;
				return false;
			}
			current = stack.pop();
			for(auto node = current.right; node !is null; node = node.left)
			{
				stack.push(node);
			}
			return true;
		}

		T currentValue()
		{
			if(current !is null)
				return current.value;
			return T.init;
		}

		initialize();
		while(moveNext())
		{
			array[i++] = currentValue();
		}
	}

	/*
	 * 其他方法
	 */

	/**
	 * 返回此 Set 中当前第一个（最低）元素。
	 * Params:
	 * 		item = 如果此 Set 为空，返回类型初始值；否则返回此 Set 最小值。
	 * Returns:
	 *		如果此 Set 为空，返回 false；否则，返回 true。
	 */
	public final bool tryGetFirst(out T item)
	{
		auto node = theTree.min();
		if(node is null)
		{
			item = T.init;
			return false;
		}
		item = node.value;
		return true;
	}

	/**
	 * 返回此 Set 中当前最后一个（最高）元素。
	 * Params:
	 * 		item = 如果此 Set 为空，返回类型初始值；否则返回此 Set 最大值。
	 * Returns:
	 *		如果此 Set 为空，返回 false；否则，返回 true。
	 */

	public final bool tryGetLast(out T item)
	{
		auto node = theTree.max();
		if(node is null)
		{
			item = T.init;
			return false;
		}
		item = node.value;
		return true;
	}

	/**
	 * 移除第一个（最低）元素。
	 * Returns:
	 *		如果此 Set 为空，返回 false;否则返回 true。
	 */
	public final bool removeFirst()
	{
		auto size = theTree.count();
		theTree.removeMin();
		if(size == theTree.count())
			return false;
		theVersion++;
		return true;
	}

	/**
	 * 移除最后一个（最高）元素。
	 * Returns:
	 *		如果此 Set 为空，返回 false;否则返回 true。
	 */
	public final bool removeLast()
	{
		auto size = theTree.count();
		theTree.removeMax();
		if(size == theTree.count())
			return false;
		theVersion++;
		return true;
	}

	/**
	 * 返回此 Set 所使用的比较器。
	 */
	public final IComparer!(T) comparer()
	{
		return theTree.comparer;
	}
}

unittest
{
	class TestTreeSet
	{
		void testCtor()
		{
			auto set = new TreeSet!(int)();

			assert( set !is null );

			set.add(1);
			set.add(2);

			assert( set.count == 2 );

			auto list = new ArrayList!(int)(3);

			list.add(1);
			list.add(2);
			list.add(3);

			set = new TreeSet!(int)(list);

			assert( set.count == 3 );
		}

		void testForEach()
		{
			auto set = new TreeSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			set.add(4);
			set.add(5);

			int i = 1;
			foreach(item; set)
			{
				assert(i++ == item);
			}

			try
			{
				foreach(item; set)
				{
					set.removeFirst();
				}
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testIsEmptyAndCount()
		{
			auto set = new TreeSet!(int)();

			assert( set.isEmpty() );
			assert( set.count == 0 );

			set.add(1);

			assert( !set.isEmpty() );
			assert( set.count == 1 );

			assert( !set.isReadOnly() );
		}

		void testAdd()
		{
			auto set = new TreeSet!(int)();
			bool result;
			result = set.add(1);
			
			assert( result == true );
			assert( set.count == 1 );
			
			result = set.add(1);
			
			assert( result == false );
			assert( set.count == 1 );
		}

		void testClear()
		{
			auto set = new TreeSet!(int)();

			set.add(1);
			set.add(2);
			set.add(3);

			set.clear();

			assert(set.isEmpty());
			assert(set.count == 0);
		}

		void testRemove()
		{
			bool result;
			auto set = new TreeSet!(int)();

			set.add(1);
			set.add(2);
			set.add(3);
			set.add(4);
			set.add(5);

			result = set.removeFirst();

			assert(result == true && set.count == 4);

			result = set.removeLast();

			assert(result == true && set.count == 3);

			result = set.remove(2);

			assert(result == true && set.count == 2);

			result = set.remove(2);

			assert(result == false && set.count == 2);
		}

		void testContains()
		{
			auto set = new TreeSet!(int)();
			set.add(1);
			set.add(2);

			assert(set.contains(1));
			assert(!set.contains(3));

			set.remove(1);

			assert(!set.contains(1));
		}

		void testToArray()
		{
			auto set = new TreeSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			set.add(4);
			set.add(5);

			int[5] array = [1,2,3,4,5];
			int[5] a;

			set.toArray(a);

			for(auto i = 0; i < a.length; i++)
			{
				assert(array[i] == a[i]);
			}
		}

		void testGetMethod()
		{
			bool result;
			int item;
			auto set = new TreeSet!(int)();

			result = set.tryGetFirst(item);

			assert(result == false && item == int.init);

			result = set.tryGetLast(item);

			assert(result == false && item == int.init);

			set.add(1);
			set.add(2);

			result = set.tryGetFirst(item);

			assert(result == true && item == 1);

			result = set.tryGetLast(item);

			assert(result == true && item == 2);
		}
	}

	auto test = new TestTreeSet();

	test.testCtor();
	test.testForEach();
	test.testIsEmptyAndCount();
	test.testAdd();
	test.testClear();
	test.testRemove();
	test.testContains();
	test.testToArray();
	test.testGetMethod();
}